package com.hk.commons.algorithm;


import java.util.HashMap;
import java.util.Objects;

/**
 * 前缀树
 *
 * @author Kevin
 * @date 2024-08-06 22:26
 */
public class PrefixTree {

    private final Node root;

    public PrefixTree() {
        this.root = new Node();
    }

    /**
     * 检查 prefix 是整个前缀树中穿梭的次数
     */
    public int search(String prefix) {
        if (Objects.isNull(prefix) || prefix.isEmpty()) {
            return 0;
        }
        Node temp = root;
        for (char item : prefix.toCharArray()) {
            if (temp.child.containsKey((int) item)) {
                temp = temp.child.get((int) item);
            } else {
                return temp.pass;
            }
        }
        return temp.pass;
    }

    /**
     * 检查指定值是否在整个前缀树中存在
     *
     * @param value 要检查的值
     */
    public boolean exists(String value) {
        if (Objects.isNull(value) || value.isEmpty()) {
            return false;
        }
        Node temp = root;
        for (char item : value.toCharArray()) {
            if (temp.child.containsKey((int) item)) {
                temp = temp.child.get((int) item);
            } else return false;
        }
        return temp.end != 0;
    }

    /**
     * 添加
     */
    public void add(String prefix) {
        if (Objects.nonNull(prefix) && !prefix.isEmpty()) {
            Node temp = root;
            temp.pass++;
            char[] chars = prefix.toCharArray();
            for (char item : chars) {
                if (root.child.containsKey((int) item)) {
                    temp = root.child.get((int) item);
                    temp.pass++;
                } else {
                    Node node = new Node();
                    node.pass = 1;
                    node.end = 1;
                    temp.child.put((int) item, node);
                }
            }
        }
    }

    public void remove(String prefix) {
        //TODO:
    }


    /**
     * 节点信息
     */
    private static class Node {

        /**
         * 记录每个char在当前节点通过的次数
         */
        private int pass;

        /**
         * 记录以当前节点结束的字符前缀个数
         */
        private int end;

        private final HashMap<Integer, Node> child = new HashMap<>();
    }

}
